package search;

/**
 * @description: 斐波那契查找算法
 * @title: FibonacciSearch
 * @author: zp
 * @date: 2021/11/27 21:44
 */
public class FibonacciSearch {
    /**
     * 斐波那契数组的长度
     */
    private final static int FIB_ARRAY_LENGTH = 10;
    /**
     * 斐波那契数组的最小长度
     */
    private final static int FIB_ARRAY_MIN_LENGTH = 3;

    public static void main(String[] args) {
        int[] array = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88, 88, 88, 88, 88};
        System.out.println(recurseFibonacciSearch(array, getFibArray(), 47, 0, array.length - 1, getFibArray(array.length)));
    }

    /**
     * @description: 获取斐波那契数组的索引
     * @author: zp
     * @date: 2021/11/27 21:57
     * @param: length
     * @return: int
     */
    private static int getFibArray(int length) {
        if (FIB_ARRAY_MIN_LENGTH < 3) {
            throw new IllegalArgumentException("斐波那契数列的最小长度为3");
        }
        int[] fibArray = new int[FIB_ARRAY_LENGTH];
        fibArray[0] = 1;
        fibArray[1] = 1;
        for (int i = 2; i < FIB_ARRAY_LENGTH; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }
        int index = 0;
        while (length > fibArray[index]) {
            index++;
        }
        return index;
    }

    /**
     * @description: 获取斐波那契数组
     * @author: zp
     * @date: 2021/11/27 21:58
     * @param:
     * @return: int[]
     */
    private static int[] getFibArray() {
        int[] fibArray = new int[FIB_ARRAY_LENGTH];
        fibArray[0] = 1;
        fibArray[1] = 1;
        for (int i = 2; i < FIB_ARRAY_LENGTH; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
        }
        return fibArray;
    }

    /**
     * 斐波那契查找（递归方式）
     *
     * @param array    待查找的数组
     * @param fibArray 斐波那契数组
     * @param key      关键字
     * @param low      低索引值
     * @param high     高索引值
     * @return int 关键字在数组的位置，未查找到，返回-1
     * @Author muyi
     * @Date 14:32 2020/12/2
     */
    public static int recurseFibonacciSearch(int[] array, int[] fibArray, int key, int low, int high, int index) {
        /**
         *  key < array[low]：小于最小值
         *  key > array[high]：大于最大值
         *  low > high：遍历整个数组均未找到元素，退出
         */
        if (array == null || array.length == 0 || key < array[low] || key > array[high] || low > high) {
            return -1;
        }

        int middle = low + fibArray[index - 1] - 1;
        if (key < array[middle]) {
            // 如果小于关键字，在黄金分隔点之前查找
            return recurseFibonacciSearch(array, fibArray, key, low, middle - 1, index - 1);
        } else if (key > array[middle]) {
            // 如果大于关键字，在黄金分割点之后查找
            return recurseFibonacciSearch(array, fibArray, key, middle + 1, high, index - 2);
        } else {
            // 若相等则说明 middle 即为查找到的位置
            if (middle <= high) {
                return middle;
                // middle的值已经大于high,进入扩展数组的填充部分,即最后一个数就是要查找的数。
            } else {
                return high;
            }
        }
    }

}
